10579. Числа Фибоначчи

Числа Фибоначчи задаются рекуррентным соотношением:

f(1) = 1, f(2) = 1, f(n) = f(n – 1) + f(n – 2)

Вход. Каждая строка содержит целое неотрицательное n.

Выход. Для каждого входного n вывести n - ое число Фибоначчи (значение f(n)). Известно, что f(n) содержит не более 1000 знаков.

Пример входа

3
100
 

Пример выхода

2

354224848179261915075

РЕШЕНИЕ

длинная арифметика + числа Фибоначчи

Анализ алгоритма

Воспользуемся классом BigInteger. Для каждого входного n вычислим значение f(n), используя приведенную в условии рекуррентную формулу.

Реализация алгоритма

Положим длину чисел MAXLENGTH равной 1001.

#define MAXLENGTH 1001

Читаем входное значение n. Изначально положим a = f(0) = 0, b = f(1) = 1. Во вложенном цикле while после выполнения i - ой итерации имеют место соотношения: a = f(i), b = f(i + 1). Выполнив цикл n раз, выводим a = f(n).

BigInteger a(0),b(1),temp(0);

int n;

while(scanf("%d",&n) == 1)

{

a = BigInteger(0); b = BigInteger(1);

while(n--) temp = a,a = b,b = temp + a;

a.print();

}